1. Field of the Invention
The present invention generally relates to tracing of shorts in very large nets in Very Large Semiconductor Integrated (VLSI) circuit designs and, more particularly, to efficiently finding one electrical path containing at least one of the VLSI design component instances causing the short. In this task, the invention relaxes the requirement of a shortest path to an approximation of a shortest path to take full advantage of the hierarchical structure of the VLSI design.
2. Background Description
The problem of tracing shorts in a design is to find an electrical path consisting out of a small number of VLSI design component instances, such that it contains at least one of the VLSI design component instances that cause the short. We refer to such a path in the following as a "shorting path". Shorts between large nets, e.g., between circuit ground (GND) and source voltage (VDD), occur frequently in designs. Although existing tools are able to detect the existence of a short in a hierarchical design, finding a shorting path in large designs is extremely time consuming. The automated tracing of shorts between very large nets by existing software tools typically fails due to extreme storage or computation time requirements.
The problem of finding a short electrical path between two VLSI design component instances with different net attributes can be mapped to finding a short path in a graph, in which the vertices correspond to VLSI design component instances and the edges correspond to VLSI direct electrical connectivity between the two adjacent vertices. Net attributes are names attached to at least one VLSI design component instance on a net, where a net is a set of VLSI design component instances which form a connected component with respect to a relation as for example intersection between the geometric shapes of which the VLSI design components are composed. Geometric shapes are the most elementary type of VLSI design components, which usually form the leaf components in the VLSI design hierarchy. In the following, we will refer to leaf components as "leafs". For detailed definitions of hierarchy, VLSI design components, nets, etc., see U.S. Pat. Nos. 5,519,628 and 5,481,473 and the reference materials, Introduction to Algorithms, by T. H. Corment, C. E. Leiserson, R. L. Rivest (MIT Press), hereafter referred to as "Algorithms", and The LEDA Platform for Combinatorial and Geometric Computing, by K. Mehlhorn, and S. Naher (Cambridge University Press), hereafter referred to as "Geometric Computing".
"Algorithms" shows that the single source shortest path problem can be solved with a Breadth First Search (BFS) in O(N) time in unweighted graphs, Dijkstra's algorithm solves it in weighted undirected graphs in O(N log N) time.
In a hierarchical design, any standard shortest path search (as BFS or Dijkstra's algorithm) cannot be applied directly without flattening the design, which results in un-processable amounts of data for large designs. The BFS and Dijkstra's algorithm requires at least two Boolean values (representable as two bits in a computer memory) per vertex, which indicate whether or not the vertex was unprocessed, touched or visited. A vertex is called visited if its outgoing edges were investigated during the algorithm. It is called touched if it was found by investigating an outgoing edge of another node. In the following, we will refer to the different flavors of shortest paths searches as "SPS". In a shortest path search in a hierarchical design, at least these Boolean variables must be stored for each instance of a leaf, i.e., flat, even when the design is not flattened before processing.
Since very large designs might contain hundreds of millions of shapes, even storing one bit per shape instance is extremely storage consuming, in addition to the indexing problem. Hence, techniques to store the state temporarily for a limited number of instances or techniques taking advantage of the hierarchical structure of the problem are necessary.